package com.goudan.practice.tree;

import java.util.HashMap;
import java.util.HashSet;

/**
 * 最低公共祖先
 * 题目：给定两个二叉树节点node1和node2，找到他们的最低公共祖先节点
 */
public class LowestCommonParent {

    private static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data) {
            this.value = data;
        }
    }

    /**
     *解法1：遍历整棵树，把所有节点的父节点都维护到一个Map中，然后找到node1的所有父节点维护到set中，
     * 再遍历node2的所有的父，第一个在set中遇到的节点就是最低公共祖先
     */
    public static Node lca(Node head, Node o1, Node o2) {
        if (head == null) {
            return null;
        }
        HashMap<Node, Node> parentMap = new HashMap<>();
        parentMap.put(head, null);
        fillParentMap(head, parentMap);
        HashSet<Node> set = new HashSet<>();
        Node cur = o1;
        set.add(cur);
        // 只有头节点才等于自己的父，如果当前节点不等于自己的父，就可以往上走
        while (null != parentMap.get(cur)) {
            cur = parentMap.get(cur);
            set.add(cur);
        }
        // o1往上所有节点都在这个set里面，只有最初的head不在里面
        cur = o2;
        while (!set.contains(cur)) {
            cur = parentMap.get(cur);
        }
        return cur;
    }

    private static void fillParentMap(Node head, HashMap<Node, Node> fatherMap) {
        if (head.left != null) {
            fatherMap.put(head.left, head);
            fillParentMap(head.left, fatherMap);
        }
        if (head.right != null) {
            fatherMap.put(head.right, head);
            fillParentMap(head.right, fatherMap);
        }
    }

    /**
     * 解法2：非常之抽象，获取公共祖先方法
     */
    public static Node lowestCommonAncestor(Node head, Node o1, Node o2) {
        if (head == null || head == o1 || head == o2) {
            return head;
        }
        Node left = lowestCommonAncestor(head.left, o1, o2);
        Node right = lowestCommonAncestor(head.right, o1, o2);
        if (left != null && right != null) {
            return head;
        }
        return left != null ? left : right;
    }




    public static void main(String[] args) {

    }
}
